#!/usr/bin/python

"""
Heapsort implementation
"""

def siftup(x, n):
    i = n
    c = x[i] #x[i] == c
    while True:
        p = i / 2
        if x[p] >= c:
            break
        x[i] = x[p]
        i = p

    x[i] = c

def siftdown(x, n):
    if n <= 1: return 
    i = 1
    c = x[i]
    while True:
        p = 2 * i
        if p > n: break
        if p + 1 <= n and x[p+1] > x[p]:
            p += 1
        if x[p] <= c:
            break
        x[i] = x[p]
        i = p # x[i] is imaginarily c

    x[i] = c

def swap(x, i, j):
    tmp = x[i]
    x[i] = x[j]
    x[j] = tmp

def Heapsort(x, n):
    """
    x is an array with x[0] as sentinel, x[1] to x[n] as valid values
    """
    for i in range(2, n+1):
        siftup(x, i)
    for i in range(n, 1, -1):
        swap(x, 1, i)
        siftdown(x, i-1)


if __name__ == '__main__':

    import unittest
    try:
        treePainter = True 
        from btree import *
    except ImportError:
        treePainter = False
        

    class heapTest(unittest.TestCase):
        @staticmethod
        def checkSorted(x):
            y = x[1:]
            y.sort()
            y.insert(0, x[0])
            if x == y:
                return True
            else:
                return False
       
        @staticmethod
        def printHeap(x, n):
            if not treePainter: return
            tree = binSearchTree()
            tree.buildFromArray(x[1:n+1])
            painter = BinTreeTextPainter()
            tree.paintTree(painter)
            painter.display()

        def runOneCase(self):
            minv = -99
            maxv = 99
            x = [maxv]
            from random import randint
            n = randint(1, 19)
            for i in range(0, n):
                x.append(randint(minv+1, maxv))
            Heapsort(x, n)
            heapTest.printHeap(x, n)
            self.assertTrue(heapTest.checkSorted(x))
            del x

        def testHeapSort(self):
            for i in range(1, 19):
                self.runOneCase()


    unittest.main()

